package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class BestTimeToBuyAndSellStock extends MaximumSubarray {

    // If you were only permitted to complete at most one transaction
    //      (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
    // Note that you cannot sell a stock before you buy one.
    //
    // [7,1,5,3,6,4]
    // [,-6,4,-2,3,-2] <= 思维转换: 考察每日价格变化
    //
    // 寻找数组的和最大的非空连续子数组
    //
    // maximum subarray
    // 两种方法:
    //
    // - 分治法: O(nlogn): A[low...mid]、A[mid+1...high]、A[low...high]
    // - 动态规划: O(n)
    //
    // ========================
    // 分治法
    // https://algorithms.tutorialhorizon.com//maximum-subarray-or-largest-sum-contiguous-subarray-problem-divide-and-conquer/
    // ========================
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int[] priceDiff = calcPriceDiff(prices);
        return maxSubArray(priceDiff);
    }

    // 关注价格变化
    private int[] calcPriceDiff(int[] prices) {
        int[] array = new int[prices.length];

        for (int i = 1; i < prices.length; i++) {
            array[i] = prices[i] - prices[i - 1];
        }

        return array;
    }

    // ========================
    // 分治法
    // Kadane's Algorithm
    // ========================
    public int maxProfitDP(int[] prices) {
        int maxCur = 0; // 当前最大值
        int maxSoFar = 0; // 当前发现的最大值

        for (int i = 1; i < prices.length; i++) {
            // 是否有贡献
            // 贡献度: (prices[i] - prices[i - 1])
            maxCur = Math.max(0, maxCur + (prices[i] - prices[i - 1]));
            maxSoFar = Math.max(maxCur, maxSoFar);
        }

        return maxSoFar;
    }

}
